6941. Сумма НОД

Для заданных n натуральных чисел a₁, a₂, …, a_n найдите сумму НОД (наибольших общих делителей) всех возможных пар этих чисел.

Вход. В первой строке задано количество тестов t (1 < t < 100). Каждый тест состоит из одной строки и содержит количество входных чисел n (1 < n < 100), за которым следуют n натуральных чисел. Все входные числа не превышают 10⁶.

Выход. Для каждого теста в отдельной строке вывести сумму НОД всех возможных пар.

Пример входа	Пример выхода
3 4 10 20 30 40 3 7 5 12 3 125 15 25	70 3 35

РЕШЕНИЕ

НОД

Анализ алгоритма

Для каждого теста занесем набор входных чисел в массив mas. Далее для каждой пары (i, j) (0 ≤ i < j < m) вычисляем НОД(mas[i], mas[j]) и прибавляем его к общей сумме.

Пример

Для третьего примера ответ равен

НОД(125,15) + НОД(125,25) + НОД(15,25) = 5 + 25 + 5 = 35

Реализация алгоритма

Входные числа храним в массиве m.

#define MAX 110

int m[MAX];

Функция gcd возвращает наибольший общий делитель чисел a и b.

int gcd(int a, int b)

{

return (!b) ? a : gcd(b, a % b);

}

Основная часть программы. Читаем количество тестов tests.

scanf("%d", &tests);

while (tests--)

{

Читаем входные данные для каждого теста.

scanf("%d", &n);

for (i = 0; i < n; i++)

scanf("%d", &m[i]);

В переменной res подсчитываем искомую сумму.

res = 0;

Перебираем все возможные пары индексов (i, j) таких что 0 ≤ i < j < n, для каждой пары вычисляем НОД(m[i], m[j]) и прибавляем это значение к res.

for (i = 0; i < n; i++)

for (j = i + 1; j < n; j++)

res += gcd(m[i], m[j]);

Выводим ответ.

printf("%d\n", res);

}

Python реализация

Читаем количество тестов tests.

tests = int(input())

Читаем входные данные для каждого теста.

for _ in range(tests):

n, *lst = list(map(int, input().split()))

В переменной res подсчитываем искомую сумму.

res = 0

Перебираем все возможные пары индексов (i, j) таких что 0 ≤ i < j < n, для каждой пары вычисляем НОД(lst[i], lst[j]) и прибавляем это значение к res.

for i in range(n):

for j in range(i + 1, n):

res += math.gcd(lst[i], lst[j])

Выводим ответ.

print(res)